|
Arithmetic in a finite field is different from standard integer arithmetic. There are a limited number of elements in the finite field; all operations performed in the finite field result in an element within that field. While no finite field itself is infinite, there are infinitely many different finite fields. Their number of elements is necessarily of the form ''pn'' where ''p'' is a prime number and ''n'' is a positive integer, and two finite fields of the same size are isomorphic. The prime ''p'' is called the characteristic of the field, and the positive integer ''n'' is called the dimension of the field over its prime field. Finite fields are used in a variety of applications, including in classical coding theory in linear block codes such as BCH codes and Reed–Solomon error correction and in cryptography algorithms such as the Rijndael encryption algorithm. ==Effective polynomial representation== The finite field with ''pn'' elements is denoted GF(''pn'') and is also called the Galois Field, in honor of the founder of finite field theory, Évariste Galois. GF(''p''), where ''p'' is a prime number, is simply the ring of integers modulo ''p''. That is, one can perform operations (addition, subtraction, multiplication) using the usual operation on integers, followed by reduction modulo ''p''. For instance, in GF(5), 4+3=7 is reduced to 2 modulo 5. Division is multiplication by the inverse modulo ''p'', which may be computed using the extended Euclidean algorithm. A particular case is GF(2), where addition is exclusive OR (XOR) and multiplication is AND. Since the only invertible element is 1, division is the identity function. Elements of GF(''pn'') may be represented as polynomials of degree strictly less than ''n'' over GF(''p''). Operations are then performed modulo ''R'' where ''R'' is an irreducible polynomial of degree ''n'' over GF(''p''), for instance using polynomial long division. The addition of two polynomials ''P'' and ''Q'' is done as usual; multiplication may be done as follows: compute ''W'' =''P''.''Q'' as usual, then compute the remainder modulo ''R'' (there exist better ways to do this). When the prime is 2, it is conventional to express elements of GF(''pn'') as binary numbers, with each term in a polynomial represented by one bit in the corresponding element's binary expression. Braces ( "" ) or similar delimiters are commonly added to binary numbers, or to their hexadecimal equivalents, to indicate that the value is an element of a field. For example, the following are equivalent representations of the same value in a characteristic 2 finite field: ;Polynomial ;Binary ;Hexadecimal 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Finite field arithmetic」の詳細全文を読む スポンサード リンク
|